// @algorithm @lc id=576 lang=cpp 
// @title out-of-boundary-paths


// #define print(...)
// @test(2,2,2,0,0)=6
// @test(1,3,3,0,1)=12
class Solution {
    const int dir[4][2] = {
        {0,1}, {1,0},
        {-1,0}, {0,-1},
    };
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        vector<vector<int>> pathMat(m, vector<int>(n, 0)); // 从起点到点[i][j]的路径数
        pathMat[startRow][startColumn] = 1;
        int ans = 0;
        for(int s=0; s<maxMove; s++){
            vector<vector<int>> mat(m, vector<int>(n, 0));
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    if(!pathMat[i][j]) continue;
                    for(auto & [dx,dy] : dir){
                        int x = i+dx, y = j+dy;
                        if(0<=x && x<m && 0<=y && y<n)
                            mat[x][y] = (pathMat[i][j] + mat[x][y]) % 1000000007;
                        else
                            ans = (ans + pathMat[i][j]) % 1000000007;
                    }
                }
            }
            pathMat = mat;
        }
        return ans;
    }
};